// #![feature(linked_list_remove)]

use std::{
    collections::{HashMap, LinkedList, hash_map::DefaultHasher}, 
    hash::Hash,
    rc::Rc,
    fmt::Debug,
};

pub struct LRUCache<K, V>
    where K: Hash + Eq + Copy + Debug , V:Debug{
    map: HashMap<K, V>,
    cache: LinkedList<K>,
    cap: usize,
}

impl <K, V> LRUCache<K, V> where K: Hash + Eq + Copy + Debug , V:Debug {
    pub fn new(size: usize) -> Self {
        Self {
            map: HashMap::new(),
            cache: LinkedList::new(),
            cap: size,
        }
    }

    pub fn get(&mut self, k: &K) -> Option<&V> {
        let v = self.map.get(k);
        if v.is_some() {
            self.make_recently(k)
        } else {
            None
        }
    }

    pub fn put(&mut self, k: K, v: V) {
        if let Some(_) = self.map.keys().into_iter().find(|&e| *e == k) {
            println!("resue: {:?}", k);
            self.make_recently(&k);
            return;
        }

        if self.cap == self.cache.len() {
            let k0 = self.cache.pop_front().unwrap();
            let v0 = self.map.remove(&k0);

            println!("arive max: delete: k:{:?}, v: {:?}", k0, v0);
        }

        self.map.insert(k, v);
        self.cache.push_back(k);
    }

    fn make_recently(&mut self, k: &K) -> Option<&V> {
        match self.map.get(k) {
            Some(_) => {
                if let Some(idx) = self.find_index(k) {
                    let kk = self.remove_from_list(idx).unwrap();
                    self.cache.push_back(kk);
                    return self.map.get(k);
                } else {
                    None
                }
                
            }
            _ => { println!("{:?} doesn't exist" , &k); None }
        }
    }

    fn delete(&mut self, k:&K) -> Option<V> {
        match self.find_index(k) {
            None => { println!("{:?} doesn't exist", k); None }
            Some(idx)=> {
                let v = self.remove_from_list(idx).unwrap();
                self.map.remove(&v)
            }
        }
    }

    fn remove_from_list(&mut self, idx: usize) -> Option<K> {
        let mut split_list = self.cache.split_off(idx);
        let v = split_list.pop_front();
        self.cache.append(&mut split_list);
        v
    }

    fn remove_least_recently(&mut self) {
        match self.cache.pop_front() {
            Some(v) => {
                self.map.remove(&v);
            },
            None => {}
        }
    }

    fn find_index(&self, k:&K) -> Option<usize> {
        for (idx, item) in self.cache.iter().enumerate() {
            if item.eq(k)  {
                return Some(idx);
            }
        }
        None
    }

    pub fn output(&self) {
        for k in self.cache.iter() {
            println!("k: {:?} v: {:?}", k, self.map.get(k).unwrap());
        }
    }
}

#[cfg(test)]
mod tests {
    use std::hash::Hasher;

    use super::*;

    #[derive(Debug, Hash)]
    struct T {
        a: u32,
        b: String,
    }

    fn calc_hash(v: impl Hash) -> u64 {
        let mut hasher = DefaultHasher::new();
        v.hash(&mut hasher);
        hasher.finish()
    }

    #[test]
    fn test_lru() {
        let mut lru = LRUCache::<u64, T>::new(3);
        let a = T{a: 1, b:"a".to_owned()};
        let b = T{a: 2, b:"b".to_owned()};
        let c = T{a: 3, b:"c".to_owned()};
        let d = T{a: 4, b:"d".to_owned()};
        let e = T{a: 5, b:"e".to_owned()};

        let values = vec![&a,&b,&c,&d];
        let mut keys = vec![];
        for v in &values {
            keys.push(calc_hash(v));
        }

        lru.put(keys[0] , a);
        lru.put(keys[1] , b);
        lru.put(keys[2] , c);

        println!("get {:?}",lru.get(&keys[1]).unwrap());

        lru.put(keys[3], d);
        lru.put(calc_hash(&e), e);
        
        lru.output();
    }
}